use crate::utils::access_guard::AccessGuard;
use std::cell::Cell;
use std::mem;
use std::ptr::NonNull;

pub(crate) struct DoubleLinkedList<T>
where
    T: DoubleLinkedNode<T>,
{
    head: Cell<Option<NonNull<T>>>,
    tail: Cell<Option<NonNull<T>>>,
}

impl<T> Default for DoubleLinkedList<T>
where
    T: DoubleLinkedNode<T>,
{
    fn default() -> Self {
        Self {
            head: Cell::new(None),
            tail: Cell::new(None),
        }
    }
}

pub(crate) trait DoubleLinkedNode<T> {
    fn next(&mut self) -> &mut Option<NonNull<T>>;
    fn prev(&mut self) -> &mut Option<NonNull<T>>;
}

impl<T> DoubleLinkedList<T>
where
    T: DoubleLinkedNode<T>,
{
    pub(crate) fn push<G>(&self, access_guard: &G, current_ptr: NonNull<T>)
    where
        G: AccessGuard<T>,
    {
        let current = access_guard.access(current_ptr);
        debug_assert!(current.prev().is_none());
        debug_assert!(current.next().is_none());
        let prev_head_ptr = self.head.replace(Some(current_ptr));
        *current.next() = prev_head_ptr;
        if let Some(prev_head_ptr) = prev_head_ptr {
            let node = access_guard.access(prev_head_ptr);
            debug_assert!(node.prev().is_none());
            *node.prev() = Some(current_ptr);
        }
        if self.tail.get().is_none() {
            self.tail.set(Some(current_ptr));
        }
    }

    pub(crate) fn first(&self) -> Option<NonNull<T>> {
        self.head.get()
    }

    pub(crate) fn leave<G>(&self, access_guard: &G, current_ptr: NonNull<T>)
    where
        G: AccessGuard<T>,
    {
        let current = access_guard.access(current_ptr);
        let next_ptr = mem::replace(current.next(), None);
        let prev_ptr = mem::replace(current.prev(), None);
        match prev_ptr {
            None => {
                debug_assert_eq!(self.head.get(), Some(current_ptr));
                self.head.set(next_ptr);
            }
            Some(prev_ptr) => {
                let prev = access_guard.access(prev_ptr);
                debug_assert_eq!(*prev.next(), Some(current_ptr));
                *prev.next() = next_ptr;
            }
        }
        match next_ptr {
            None => {
                debug_assert_eq!(self.tail.get(), Some(current_ptr));
                self.tail.set(prev_ptr);
            }
            Some(next_ptr) => {
                let next = access_guard.access(next_ptr);
                debug_assert_eq!(*next.prev(), Some(current_ptr));
                *next.prev() = prev_ptr;
            }
        }
    }

    pub(crate) fn join_tail<G>(&self, access_guard: &G, another: DoubleLinkedList<T>)
    where
        G: AccessGuard<T>,
    {
        let another_head_ptr = another.head.get();
        let another_tail_ptr = another.tail.get();
        if another_head_ptr.is_none() || another_tail_ptr.is_none() {
            debug_assert!(another_head_ptr.is_none() && another_tail_ptr.is_none());
            return;
        }
        let another_head_ptr = another_head_ptr.unwrap();
        let another_tail_ptr = another_tail_ptr.unwrap();
        match self.tail.get() {
            None => {
                debug_assert!(self.head.get().is_none());
                self.head.set(Some(another_head_ptr));
                self.tail.set(Some(another_tail_ptr));
            }
            Some(tail_ptr) => {
                let tail = access_guard.access(tail_ptr);
                debug_assert!(tail.next().is_none());
                *tail.next() = Some(another_head_ptr);

                let another_head = access_guard.access(another_head_ptr);
                debug_assert!(another_head.prev().is_none());
                *another_head.prev() = Some(tail_ptr);
                self.tail.set(Some(another_tail_ptr));
            }
        }
    }

    #[cfg(test)]
    pub(crate) fn give_up_all<G>(self, guard: &G)
    where
        G: AccessGuard<T>,
    {
        let mut current = self.first();
        while let Some(node_ptr) = current {
            let node = guard.access(node_ptr);
            current = node.next().take();
            node.prev().take();
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::utils::access_guard::AccessGuard;
    use crate::utils::double_linked_list::{DoubleLinkedList, DoubleLinkedNode};
    use std::iter;
    use std::ptr::NonNull;

    struct TestNode {
        next: Option<NonNull<TestNode>>,
        prev: Option<NonNull<TestNode>>,
    }

    impl DoubleLinkedNode<TestNode> for TestNode {
        fn next(&mut self) -> &mut Option<NonNull<TestNode>> {
            &mut self.next
        }

        fn prev(&mut self) -> &mut Option<NonNull<TestNode>> {
            &mut self.prev
        }
    }

    struct TestAccessGuard;

    impl AccessGuard<TestNode> for TestAccessGuard {
        fn before_access(&self, _ptr: NonNull<TestNode>) {}
    }

    fn assert_list<T, G>(guard: &G, list: &DoubleLinkedList<T>, nodes: &Vec<T>, expected: &[usize])
    where
        G: AccessGuard<T>,
        T: DoubleLinkedNode<T>,
    {
        let mut node_idx = 0;
        let mut current = list.first();
        while let Some(node_ptr) = current {
            let node = guard.access(node_ptr);
            assert_eq!(node_ptr, NonNull::from(&nodes[expected[node_idx]]));
            match node.prev() {
                None => assert_eq!(list.head.get().unwrap(), node_ptr),
                Some(prev_ptr) => {
                    let prev_next_ptr = guard.access(*prev_ptr).next().unwrap();
                    assert_eq!(prev_next_ptr, node_ptr);
                }
            }
            match node.next() {
                None => assert_eq!(list.tail.get().unwrap(), node_ptr),
                Some(next_ptr) => {
                    let next_prev_ptr = guard.access(*next_ptr).prev().unwrap();
                    assert_eq!(next_prev_ptr, node_ptr);
                }
            }
            node_idx += 1;
            current = *node.next();
        }
        assert_eq!(node_idx, expected.len());
        assert_eq!(expected.is_empty(), list.head.get().is_none());
        assert_eq!(expected.is_empty(), list.tail.get().is_none());
        assert_eq!(list.head.get().is_none(), list.tail.get().is_none());
    }

    #[test]
    fn test_double_linked_list() {
        let guard = TestAccessGuard;
        let nodes = iter::repeat(0)
            .take(5)
            .map(|_| TestNode {
                next: None,
                prev: None,
            })
            .collect::<Vec<_>>();
        let list = DoubleLinkedList::default();

        // Test empty list
        assert_list(&guard, &list, &nodes, &[]);
        list.push(&guard, NonNull::from(&nodes[0]));
        assert_list(&guard, &list, &nodes, &[0]);
        list.leave(&guard, NonNull::from(&nodes[0]));
        assert_list(&guard, &list, &nodes, &[]);

        // push many nodes
        nodes.iter().for_each(|node| {
            list.push(&guard, NonNull::from(node));
        });
        assert_list(&guard, &list, &nodes, &[4, 3, 2, 1, 0]);

        // 脱离头节点
        list.leave(&guard, NonNull::from(&nodes[4]));
        assert_list(&guard, &list, &nodes, &[3, 2, 1, 0]);

        // 脱离尾节点
        // list: [3, 2, 1]
        list.leave(&guard, NonNull::from(&nodes[0]));
        assert_list(&guard, &list, &nodes, &[3, 2, 1]);

        // 脱离中间节点
        list.leave(&guard, NonNull::from(&nodes[2]));
        assert_list(&guard, &list, &nodes, &[3, 1]);

        // 测试 join_tail
        // 空列表 join 空列表
        let list1 = DoubleLinkedList::default();
        list1.join_tail(&guard, DoubleLinkedList::default());
        assert_list(&guard, &list1, &nodes, &[]);

        // 空列表 join 正常列表
        list1.join_tail(&guard, list);
        assert_list(&guard, &list1, &nodes, &[3, 1]);

        // 正常列表 join 空列表
        list1.join_tail(&guard, DoubleLinkedList::default());
        assert_list(&guard, &list1, &nodes, &[3, 1]);

        // 生成新列表
        let list2 = DoubleLinkedList::default();
        [4, 0, 2].into_iter().for_each(|idx| {
            list2.push(&guard, NonNull::from(&nodes[idx]));
        });
        assert_list(&guard, &list2, &nodes, &[2, 0, 4]);

        // 正常列表 join 正常列表
        list1.join_tail(&guard, list2);
        assert_list(&guard, &list1, &nodes, &[3, 1, 2, 0, 4]);
    }
}
